Head-of-line blocking

Head-of-line blocking (HOL blocking) is a performance-limiting phenomenon that occurs in buffered telecommunication network switches.

Contents

Description

A switch may be composed of buffered input ports, a switch fabric and buffered output ports. If First-in first-out (FIFO) input buffers are used, only the oldest packet is available for forwarding. More recent arrivals cannot be forwarded if the oldest packet cannot be forwarded because its destination output is busy. Without HOL blocking, the new arrivals could potentially be forwarded around the stuck packet to their respective destinations. The phenomenon can have severe performance-degrading effects in input-buffered systems.

Effect on switch performance

This phenomenon limits the throughput of switches. For FIFO input buffers, a simple model of fixed-sized cells to uniformly distributed destinations, causes the throughput to be limited to 58.6% of the total as the number of links becomes large.[1]

HOL can significantly increase packet reordering.[2]

Overcoming HOL blocking

One way to overcome this limitation is by using Virtual Output Queues.[3] Only switches with input buffering can suffer HOL blocking. With sufficient internal bandwidth, input buffering is unnecessary; all buffering is handled at outputs and HOL blocking is avoided. This no-input-buffering architecture is common in small to medium sized Ethernet switches.

See also

References

  1. ^ M. Karo; M. Hluchyj; S. Morgan (December 1987). "Input Versus Output Queuing on a Space-Division Packet Switch". IEEE Transactions on Communications 35 (12): 1347–1356. doi:10.1109/TCOM.1987.1096719. 
  2. ^ Jon C. R. Bennett; Craig Partridge; Nicholas Shectman (December 1999). "Packet reordering is not pathological network behavior". IEEE/ACM Transactions on Networking (TON) 7 (6): 789–798. doi:10.1109/90.811445. 
  3. ^ Nick McKeown; Adisak Mekkittikul; Venkat Anantharam; Jean Walrand (August 1999). "Achieving 100% Throughput in an Input-Queued Switch". IEEE Transactions on Communications 47 (8): 1260–1267. doi:10.1109/26.780463. http://tiny-tera.stanford.edu/~nickm/papers/IEEE_COMM_V3.pdf.